#include <iostream>
#include <iomanip>
using namespace std;

void Display(const int* data, int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<setw(4)<<data[i];
    }
    cout<<endl;
}

void BubbleSort(int *data, int n)
{
    int i, j, tmp;
    for(i=1; i<n; i++)
    {
        int flag = 1;
        for(j=n-1; j>i-1; j--)
        {
            if(data[j]<data[j-1])
            {
                tmp = data[j];
                data[j] = data[j-1];
                data[j-1] = tmp;
                flag = 0;
            }
        }
        cout<<"第"<<setw(2)<<i+1<<"趟排序\n";
        Display(data, n);
        if(flag) break;
    }
}

void SelectSort(int* data, int n)
{
    for(int i=0; i<n-1; i++)
    {
        int min = data[i];
        for(int j=i+1; j<n; j++)
        {
            if(min > data[j])
            {
                int tmp = min;
                min = data[j];
                data[j] = tmp;
            }
        }
        data[i] = min;
        cout<<"第"<<setw(2)<<i+1<<"趟排序\n";
        Display(data, n);        
    }
}

void InsertSort(int* data, int n)
{
    for(int i=1; i<n; i++)
    {
        int tmp = data[i];
        int j = i-1;
        for(; j>-1&&tmp<data[j]; j--)
        {
            data[j+1] = data[j];
        }
        data[j+1] = tmp;
        cout<<"第"<<setw(2)<<i<<"趟排序\n";
        Display(data, n);          
    }
}

void QuickSort(int *data, int zz, int yy, int n)
{
    int static i=0;
    int z,y,k;
    if(zz < yy)
    {
        z = zz, y = yy, k = data[z];
        do
        {
            while(z<y && data[y]>k) y--;
            if(z<y)
            {
                data[z] = data[y];
                z++;
            }

            while(z<y && data[z]<k) z++;
            if(z<y)
            {
                data[y] = data[z];
                y--; 
            }
        }while(z!=y);
        data[z] = k;
        cout<<"第"<<setw(2)<<++i<<"趟排序\n";
        Display(data, n);
        QuickSort(data,zz,z-1,n);
        QuickSort(data,z+1,yy,n);
    }
}

#include <string.h>
/**
 * @brief 合并两个有序的数组
 * 
 * @param sort1 
 * @param len1 
 * @param sort2 
 * @param len2 
 * @param join 
 */
void Join(int* sort1,int len1, int* sort2, int len2, int* join)
{
    int len3 = len1+len2, index1 = 0, index2 = 0;
    for (size_t i = 0; i < len3; i++)
    {
        int s1, s2;
        if (index1 == len1)
        {
            s1 = sort2[len2-1];
        }
        else
        {
            s1 = sort1[index1];
        }

        if (index2 == len2)
        {
            s2 = sort1[len1-1];
            break;
        }
        else
        {
            s2 = sort2[index2];
        }
        
        
        if (s1 > s2)
        {
            join[i] = s2;
            index2++;
        }
        else
        {
            join[i] = s1;
            index1++;
        }
    }
}
int main()
{
    int data[] = {4,5,3,6,2,1,8,2};
    cout<<"原始数据\n";
    Display(data, sizeof(data)/sizeof(int));
    //printf("QuickSort\n");
    //QuickSort(data, 0, sizeof(data)/sizeof(int)-1, sizeof(data)/sizeof(int));
    //printf("\n\nInsertSort\n");
    //InsertSort(data, sizeof(data)/sizeof(int));
    //printf("\n\nselectsort\n");
    //SelectSort(data, sizeof(data)/sizeof(int));
    printf("\n\nbubblesort\n");
    BubbleSort(data, sizeof(data)/sizeof(int));

    int data2[] = {9,8,7,46,52,61,18,212};
    printf("\n\nselectsort\n");
    SelectSort(data2, sizeof(data2)/sizeof(int));

    int data3[sizeof(data)/sizeof(int)+sizeof(data2)/sizeof(int)];
    Join(data, sizeof(data)/sizeof(int), data2, sizeof(data2)/sizeof(int), data3);
    printf("\n\nafter join\n");
    Display(data3, sizeof(data3)/sizeof(int));
    return 0;
}